package top.hkyzf.study.leetcode.dp;

import org.junit.Test;

/**
 * @author 朱峰
 * @date 2022-2-17 8:34
 */
public class 骑士在棋盘上的概率_688 {
    double result = 0.0;
    public double knightProbability1(int n, int k, int row, int column) {
        calcProbability(n, k, row, column, 1.0);
        return result;
    }

    void calcProbability(int n, int k, int row, int column, double preVal) {
        if (k == 0) {
            result += preVal;
            return;
        }
        int[] dX = {-1, 1, 2, 2, 1, -1, -2, -2};
        int[] dY = {-2, -2, -1, 1, 2, 2, 1, -1};
        // 计算当前点概率
        for (int i = 0; i < 8; i++) {
            int newX = row + dX[i];
            int newY = column + dY[i];
            if (newX >= 0 && newX < n && newY >= 0 && newY < n) {
                calcProbability(n, k-1, newX, newY, preVal / 8.0);
            }
        }
    }

    public double knightProbability(int n, int k, int row, int column) {
        double[][][] dp = new double[k+1][n][n];
        int[] dX = {-1, 1, 2, 2, 1, -1, -2, -2};
        int[] dY = {-2, -2, -1, 1, 2, 2, 1, -1};
        for (int i = 0; i <= k; i++) {
            for (int j = 0; j < n; j++) {
                for (int l = 0; l < n; l++) {
                    if (i == 0) {
                        dp[i][j][l] = 1;
                    } else {
                        for (int m = 0; m < 8; m++) {
                            int newX = j + dX[m];
                            int newY = l + dY[m];
                            if (newX >= 0 && newX < n && newY >= 0 && newY < n) {
                                dp[i][j][l] += dp[i-1][newX][newY] / 8.0;
                            }
                        }
                    }
                }
            }
        }
        return dp[k][row][column];
    }

    @Test
    public void testKnightProbability () {
        int n=10, k=13, row=5, column=3;
        System.out.println(knightProbability(n, k, row, column));
    }
}
